﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;
using System.Diagnostics;

namespace XNADota.Graphics
{
    class OctTree
    {
        private const int ChildrenCount = 8;
        private const int MaxCount = 64;

        private OctTree[] _ChildrenOctTrees;
        private BoundingBox _BoundingBox;
        private int _CurrentDepth;
        private bool _IsLeave;
        private int _PaletteInstanceArrayCount;
        private PaletteInstance[] _PaletteInstanceArray;

        public void CheckBoundingBox()
        {

        }

        public int PrintDebugInfo()
        {
            return 0;
#if bdw
            string Prefix = (_IsLeave ? "Leave   " : "Branch  ") + _CurrentDepth.ToString() ;
            for (int i = 0; i < _CurrentDepth; i++)
                Prefix = Prefix + "   ";

            Debug.WriteLine(Prefix + _BoundingBox);
            if (_IsLeave)
            {
                if (_PaletteInstanceArray.Count != 0)
                    Debug.WriteLine(Prefix + "Leaves Count: " + _PaletteInstanceArray.Count);
                for (int i = 0; i < _PaletteInstanceArray.Count; i++)
                    Debug.WriteLine("     " + _PaletteInstanceArray[i].Position + "  " + this.IsInBoundingBox(_PaletteInstanceArray[i]));

                return _PaletteInstanceArray.Count;
            }
            else
            {
                int TotalCount = 0;
                if (_PaletteInstanceArray.Count != 0)
                {
                    Debug.WriteLine(Prefix + "Leaves Count: " + _PaletteInstanceArray.Count);
                    TotalCount = _PaletteInstanceArray.Count;
                }

                for (int i = 0; i < _ChildrenOctTrees.Length; i++)
                    TotalCount += _ChildrenOctTrees[i].PrintDebugInfo();
                Debug.WriteLine(Prefix + " Total Count " + TotalCount);
                return TotalCount;
            }
#endif
        }

        public OctTree(BoundingBox BoundingBox, int Depth)
        {
            _BoundingBox = BoundingBox;
            _CurrentDepth = Depth;
            _IsLeave = true;

            if (_IsLeave == true)
            {
                _ChildrenOctTrees = null;
                _PaletteInstanceArray = new PaletteInstance[MaxCount];
            }
        }

        public void Update(BoundingFrustum BoundingFrustum)
        {
            if (_IsLeave == false && _PaletteInstanceArrayCount > 0)
            {
                for (int index = 0; index < _PaletteInstanceArrayCount; index++)
                {
                    _PaletteInstanceArray[index].Update(BoundingFrustum);
                    if (_PaletteInstanceArray[index].IsVisible)
                        SceneManager.Instance.AddIntoRenderQueue(_PaletteInstanceArray[index]);
                }
            }

            if (BoundingFrustum.Contains(this._BoundingBox) == ContainmentType.Disjoint)
                return;

            if (_IsLeave)
            {
                for (int index = 0; index < _PaletteInstanceArrayCount; index++)
                {
                    _PaletteInstanceArray[index].Update(BoundingFrustum);
                    if (_PaletteInstanceArray[index].IsVisible)
                        SceneManager.Instance.AddIntoRenderQueue(_PaletteInstanceArray[index]);
                }
            }
            else
            {
                foreach (OctTree childTree in _ChildrenOctTrees)
                    childTree.Update(BoundingFrustum);
            }
        }

        public bool InsertPaletteInstance(PaletteInstance Instance)
        {
            Debug.Assert(Instance != null);

            bool success = false;
            if (!IsInBoundingBox(Instance))
                return false;

            if (_IsLeave == true)
            {
                success = true;
                _PaletteInstanceArray[_PaletteInstanceArrayCount] = Instance;
                _PaletteInstanceArrayCount++;

                // If it's out of range
                if (_PaletteInstanceArrayCount >= MaxCount)
                {
                    Expand();
                }
            }
            else
            {
                // Insert into next level
                for (int i = 0; i < ChildrenCount; i++)
                    if (_ChildrenOctTrees[i].InsertPaletteInstance(Instance))
                    {
                        success = true;
                        break;
                    }

                // Stay in this level
                if (success == false)
                {
                    _PaletteInstanceArray[_PaletteInstanceArrayCount] = Instance;
                    _PaletteInstanceArrayCount++;
                    success = true;

                    if (_PaletteInstanceArrayCount > MaxCount)
                        throw new InvalidOperationException("Can not insert palette instance bacause it's out of max size");
                }
            }

            Debug.Assert(success);
            return success;
        }

        public bool IsInBoundingBox(PaletteInstance Instance)
        {
            return Instance.BeContained(this._BoundingBox) == ContainmentType.Contains;
        }

        private void Expand()
        {
            _IsLeave = false;

            // Create children
            _ChildrenOctTrees = new OctTree[ChildrenCount];

            for (int x = 0; x < 2; x++)
                for (int y = 0; y < 2; y++)
                    for (int z = 0; z < 2; z++)
                    {
                        Vector3 Min = new Vector3
                        (
                            x == 0 ? _BoundingBox.Min.X : (_BoundingBox.Min.X + _BoundingBox.Max.X) / 2,
                            y == 0 ? _BoundingBox.Min.Y : (_BoundingBox.Min.X + _BoundingBox.Max.Y) / 2,
                            z == 0 ? _BoundingBox.Min.Z : (_BoundingBox.Min.X + _BoundingBox.Max.Z) / 2
                        );
                        Vector3 Max = new Vector3
                        (
                            x == 1 ? _BoundingBox.Max.X : (_BoundingBox.Min.X + _BoundingBox.Max.X) / 2,
                            y == 1 ? _BoundingBox.Max.Y : (_BoundingBox.Min.X + _BoundingBox.Max.Y) / 2,
                            z == 1 ? _BoundingBox.Max.Z : (_BoundingBox.Min.X + _BoundingBox.Max.Z) / 2
                        );

                        int index = x << 2 | y << 1 | z;
                        _ChildrenOctTrees[index] = new OctTree(new BoundingBox(Min, Max), _CurrentDepth + 1);
                    }

            // checker
            int StayHereCount = 0;

            // Insert current leave content nodes into next level
            for (int i = 0; i < _PaletteInstanceArrayCount; i++)
            {
                bool success = false;
                for (int index = 0; index < 8; index++)
                    if (_ChildrenOctTrees[index].InsertPaletteInstance(_PaletteInstanceArray[i]))
                    {
                        _PaletteInstanceArray[i] = null;
                        success = true;
                        break;
                    }
                if (success == false)
                    StayHereCount++;
            }

            // Remove all null elements in array
            _PaletteInstanceArrayCount = 0;
            for (int i = 0; i < _PaletteInstanceArray.Length; i++)
                if (_PaletteInstanceArray[i] != null)
                {
                    _PaletteInstanceArray[_PaletteInstanceArrayCount] = _PaletteInstanceArray[i];
                    _PaletteInstanceArrayCount++;
                }

            for (int i = _PaletteInstanceArrayCount + 1; i < _PaletteInstanceArray.Length; i++)
                _PaletteInstanceArray[i] = null;

            // validate the correction of this operation.
            Debug.Assert(_PaletteInstanceArrayCount == StayHereCount);
        }
    }
}
